一道神奇的线段树...
题目要求区间修改,区间查询,很容易想到线段树,但是怎么维护每一位数字呢?
显然,我们将每位拆分,对于每一个数字维护他的贡献,如 中 的贡献为 , 的贡献为 。于是,我们需要棵线段树,维护的贡献。
修改很简单,如果将改为,注意区间有懒标记时要比较懒标记(因为该区间的数字在下传时会变),将区间懒标记为的改为,统计贡献,同时更改懒标记。
最后统计答案时,将区间数字的贡献乘上该位的数字,求和即可。
最关键的是懒标记下传,将子树懒标记不同的加入到贡献里,再将子树懒标记修改,注意改变后可能会影响答案,建议先用变量存储再赋值。
#include <cstdio>
#define ls x << 1
#define rs x << 1 | 1
const int MAXN = 100000;
int n , k , a[ MAXN + 5 ];
struct Point{
int l , r , Lazy;
long long sum;
};
struct Segment_Tree{
Point Tree[ 10 ][ 4 * MAXN + 5 ];
void Pushup( int x ) {
for( int i = 0 ; i <= 9 ; i ++ )
Tree[ i ][ x ].sum = Tree[ i ][ ls ].sum + Tree[ i ][ rs ].sum;
}
void Pushdown( int x ) {
int lazy[ 15 ];
long long sum[ 15 ];
for( int i = 0 ; i <= 9 ; i ++ )
lazy[ i ] = Tree[ i ][ ls ].Lazy , sum[ i ] = Tree[ i ][ ls ].sum;
for( int i = 0 ; i <= 9 ; i ++ ) {
if( Tree[ i ][ x ].Lazy == i ) continue;
for( int j = 0 ; j <= 9 ; j ++ )
if( Tree[ j ][ ls ].Lazy == i ) lazy[ j ] = Tree[ i ][ x ].Lazy;
sum[ Tree[ i ][ x ].Lazy ] += Tree[ i ][ ls ].sum;
sum[ i ] -= Tree[ i ][ ls ].sum;
}
for( int i = 0 ; i <= 9 ; i ++ )
Tree[ i ][ ls ].Lazy = lazy[ i ] , Tree[ i ][ ls ].sum = sum[ i ];
for( int i = 0 ; i <= 9 ; i ++ )
lazy[ i ] = Tree[ i ][ rs ].Lazy , sum[ i ] = Tree[ i ][ rs ].sum;
for( int i = 0 ; i <= 9 ; i ++ ) {
if( Tree[ i ][ x ].Lazy == i ) continue;
for( int j = 0 ; j <= 9 ; j ++ )
if( Tree[ j ][ rs ].Lazy == i ) lazy[ j ] = Tree[ i ][ x ].Lazy;
sum[ Tree[ i ][ x ].Lazy ] += Tree[ i ][ rs ].sum;
sum[ i ] -= Tree[ i ][ rs ].sum;
}
for( int i = 0 ; i <= 9 ; i ++ )
Tree[ i ][ rs ].Lazy = lazy[ i ] , Tree[ i ][ rs ].sum = sum[ i ];
for( int i = 0 ; i <= 9 ; i ++ )
Tree[ i ][ x ].Lazy = i;
}
void Build( int x , int l , int r ) {
for( int i = 0 ; i <= 9 ; i ++ ) {
Tree[ i ][ x ].l = l , Tree[ i ][ x ].r = r;
Tree[ i ][ x ].sum = 0 , Tree[ i ][ x ].Lazy = i;
}
if( l == r ) {
int t = 1;
while( a[ l ] ) {
Tree[ a[ l ] % 10 ][ x ].sum += t;
a[ l ] /= 10 , t *= 10;
}
return;
}
int Mid = ( l + r ) / 2;
Build( ls , l , Mid );
Build( rs , Mid + 1 , r );
Pushup( x );
}
void Insert( int x , int l , int r , int dex1 , int dex2 ) {
if( r < Tree[ 0 ][ x ].l || Tree[ 0 ][ x ].r < l )
return;
if( l <= Tree[ 0 ][ x ].l && Tree[ 0 ][ x ].r <= r ) {
for( int i = 0 ; i <= 9 ; i ++ )
if( Tree[ i ][ x ].Lazy == dex1 ) {
Tree[ dex2 ][ x ].sum += Tree[ dex1 ][ x ].sum;
Tree[ dex1 ][ x ].sum = 0;
Tree[ i ][ x ].Lazy = dex2;
}
return;
}
Pushdown( x );
Insert( ls , l , r , dex1 , dex2 );
Insert( rs , l , r , dex1 , dex2 );
Pushup( x );
}
long long Find( int x , int l , int r ) {
if( r < Tree[ 0 ][ x ].l || Tree[ 0 ][ x ].r < l )
return 0;
if( l <= Tree[ 0 ][ x ].l && Tree[ 0 ][ x ].r <= r ) {
long long Ans = 0;
for( int i = 0 ; i <= 9 ; i ++ )
Ans += Tree[ i ][ x ].sum * i;
return Ans;
}
Pushdown( x );
return Find( ls , l ,r ) + Find( rs , l , r );
}
}Tree;
int op , x , y , l , r;
int main( ) {
scanf("%d %d",&n,&k);
for( int i = 1 ; i <= n ; i ++ )
scanf("%d",&a[ i ]);
Tree.Build( 1 , 1 , n );
for( int i = 1 ; i <= k ; i ++ ) {
scanf("%d",&op);
if( op == 1 ) {
scanf("%d %d %d %d",&l,&r,&x,&y);
if( x == y ) continue;
Tree.Insert( 1 , l , r , x , y );
}
if( op == 2 ) {
scanf("%d %d",&l,&r);
printf("%lld\n",Tree.Find( 1 , l , r ));
}
}
return 0;
}